The present invention relates generally to routing communications within a computer network, and more specifically, to a method and system for finding shared risk diverse paths.
Communication in a computer network involves the exchange of data between two or more entities interconnected by communication links and subnetworks. Entities concerned primarily with the correct routing of information in the network are called routers, to distinguish them from end systems which process traffic but do not take part in routing it. There are two fundamentally different approaches to the distribution and use of routing information in a network, called Distance Vector Routing and Link State Routing. In the former, each router tells its immediate neighbors how it would reach each entity in the network, updating this as similar information is received from its neighbors. In the latter, each router arranges to send information about its own connectivity to its neighbors to all routers in the network. Each router then runs an algorithm called Shortest Path First (SPF) to find the best route from itself to each entity in the network. Early routing protocols (e.g. RIP) used the Distance Vector approach. Link State Routing protocols first appeared in the early 1980s, and became widely used in the Internet during the 1990s. OSPF (Open Shortest Path First) and Integrated IS-IS (Intermediate System-Intermediate System) are widely used examples of such protocols. Although there are many detailed differences between them, the fundamental algorithms are the same for both of them. OSPF is a routing protocol developed for IP (Internet Protocol). IS-IS was originally designed for Open Systems Interconnection (OSI) protocols, and was subsequently extended to deal with IP.
With link state routing, each router must discover its neighbors and learn their network addresses. A cost (typically related to the link bandwidth) is associated, generally by network management, with each link. One or more link state packets are then constructed containing this information, and flooded to all routers in the network. Dijkstra's Shortest Path First algorithm is then used at each router to find the shortest path to every other router. This algorithm maintains a set of nodes whose shortest path is already known and operates by adding one node to this known set with each iteration. The next step is to the next closest router along this path, always choosing the one which has the lowest cost from the local node. This process continues until all reachable nodes are in the known set with costs assigned to each. If a failure occurs along the shortest path, a backup route is identified.
Network failures include, for example, node failure due to equipment breakdown or equipment damage and link failure due to inadvertent fiber cable cut. Service disruption due to a network failure can cause customers significant loss of revenue during the network down time, thus network survivability against physical failures is important. In order to provide highly available circuits, carriers establish diversely routed back up paths. Routing diversity is needed to achieve the reliability and survivability expected of modern transport networks. Algorithms currently exist for finding simple node and link diverse paths. This strategy assumes that the failure of a particular link or node is an independent event. However, due to the fact that links often share facilities such as muxes, fibers or conduits, such an assumption is not always true.
Manual provisioning techniques are commonly used to ensure routing diversity. Implicitly in the provisioning operation is the notion of a Shared Risk Link Group (SRLG). SRLG is a relatively new concept that has been introduced to provide inputs necessary to plan for reliability in transport networks (see, for example, S. Chaudhuri et al., “Control of Lightpaths in an Optical Network”, IETF Internet Draft, February 2000). A SRLG is a group of links that shat share a component whose failure causes the failure of all links of the group. The SRLG is associated with an entity at risk, typically a fiber span, and is a union of all links that ride on the fiber span. Links may traverse multiple fiber spans, and thus be in multiple SRLGs. In order to identify SRLGs, links are tagged with a token which indicates a particular facility which is at risk of failure. For example, a particular conduit may have a token ‘45’ and any circuit that passes through that conduit would carry the token ‘45’ (among a possible long list of other tokens). All of the links that carry this token are part of a SRLG. When looking for backup routes, a route which is independent of any SRLG that is associated with the primary path is sought.
Internet Gateway Protocols (IGPs) such as Open Shortest Path Forwarding (OSPF) may be used to propagate SRLGs and other physical link attributes. Neighbor discovery techniques are used to determine adjacent node connectivity. This local resource information is then advertised throughout the network via the IGP. Using this information, each node can obtain a complete view of the network. However, these techniques do not address SRLGs or diversity in routing.